//
// Created by Administrator on 2021/5/29.
//
#include <iostream>
#include <unordered_set>

using namespace std;
// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class FindElements {
private:
    unordered_set<int>us;
public:
    FindElements(TreeNode *root) {
        root->val = 0;
        dfs(root);
    }
    void dfs(TreeNode * root){
        if (root == nullptr) return;
        us.insert(root->val);
        if (root->left != nullptr) {
            root->left->val = 2 * root->val + 1 ;
            dfs(root->left);
        }
        if (root->right != nullptr){
            root->right->val = 2 * root->val+2;
            dfs(root->right);
        }
    }
    bool find(int target) {
        return us.find(target) != us.end();
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */
int main() {
    auto n1 = TreeNode(-1), n2 = TreeNode(-1), n3 = TreeNode(-1),
            n4 = TreeNode(-1), n5 = TreeNode(-1);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    auto obj = new FindElements(&n1);
    cout << obj->find(1) << endl;
    cout << obj->find(2) << endl;
}